This disclosure relates to data processing, and more specifically, to decoding data encoded utilizing binary symmetry-invariant product codes (e.g., half or quarter product codes), for example, in data storage systems or data communication systems.
Error-correction encoding is employed in data storage systems and data communication systems to improve the accuracy with which data can be recovered from a data channel. By encoding data in accordance with an error-correction code (ECC) before supplying the data to the channel, errors at the channel output can be identified and corrected to an extent dependent on the properties of the ECC. Numerous such ECC schemes are known. One well-known class of ECC scheme is based on product codes. A product code uses two component ECC codes to encode rows and columns of a notional two-dimensional array of input data.
The basic structure of a conventional product code is illustrated schematically in FIG. 1. The input data symbols (which in general may be qary symbols, having q possible symbol values, where q≥2) are assigned to respective symbol locations in a notional array having n2 rows and n1 columns of symbol locations. In this example, k2×k1 data symbols are assigned to respective locations in a k2 by k1 subarray at the intersection of the first k2 rows and first k1 columns of the n2 by n1 array. The resulting array of input data symbols is encoded by separately encoding the rows and columns of the array. A first ECC code C1 is used to encode the k1-symbol data word in each row of the array into a length-n1 C1 codeword. This example uses systematic encoding, whereby the input data is retained in the codeword. In particular, the n1 code symbols of a C1 codeword are obtained by adding (n1−k1) parity symbols after the k1-symbol data word in a given row. A second ECC code C2 is then used to encode the k2-symbols in each column of the array into a length-n2 C2 codeword, here by adding (n2−k2) parity symbols at the end of each column. The resulting n2×n1 code symbols in the array form the output codeword of the product code. In an extension of this basic idea, an interleaved product code applies the C2 code over s>1 evenly spaced columns of the array, resulting in n1/s C2 codewords.
Product codes can offer practical encoder/decoder implementations, their decoders being hard-decision based and thus avoiding the various complexity and latency issues associated with soft-decision decoding. Some decoders for interleaved product codes use the technique of iterative decoding based on a graph defined from the basic code structure. Briefly, a bipartite graph can be defined with n2 right nodes, each corresponding to a C1 codeword, and n1/s left nodes corresponding to respective C2 codewords. Each right node is connected to each left node by s edges. The s edges connecting a pair of nodes represent the s common symbols at the intersections of the C1 and C2 codewords for those nodes in the notional array described above. Iterative decoding is performed based on the graph by decoding the C1 codewords one-by-one, then decoding the C2 codewords one-by-one. Each time a codeword is successfully decoded, the edges leaving the appropriate node are corrected. The process iterates until decoding is complete, that is, either no more errors are detected by the decoder or a predetermined maximum number of iterations has been reached, in which case, the decoder may declare a decoding failure.
Another ECC scheme based on product codes is proposed in the context of optical transmission networks (OTNs) in J. Justesen, “Error correcting coding for OTN,” IEEE Communications Magazine, September 2010, and J. Justesen, Performance of Product Codes and Related Structures with Iterative Decoding, IEEE Transactions on Communications, 2011. These codes, referred to as half product codes (HPCs), are product codes which use identical codes for the row code C1 and the column code C2. If each component code C1 and C2 is a rate k/n code with a code length (i.e., number of symbols in a codeword) of n, and a dimension (i.e., number of data symbols encoded into each codeword) of k, then the resulting product code C has length N=n2, dimension K=k2, and rate (k/n)2. A codeword of C can be defined by an (n by n)-symbol matrix X corresponding to the notional array described above, where each row and column of X is a codeword of the row/column code. The corresponding half product code CH is then defined by CH={X−XT:X∈C}, where XT is the transpose matrix of X.
Note that if X is a codeword then so is XT because the row and column codes are the same. By construction, every codeword YH of CH has a zero diagonal (where the diagonal is defined here as the line of symbols extending diagonally across the (n by n)-symbol matrix YH from the top left symbol to the bottom right symbol). That is, all symbols on the diagonal are of value zero. Since it follows from the definition of CH that YH=YHT, the set of n(n−1)/2 symbols in the triangular subarray on each side of the diagonal is the same. These n(n−1)/2 symbols thus define the codeword YH whereby the half product code has an effective length of NH=n(n−1)/2. With HPCs, encoding and iterative decoding is performed in the same manner as for product codes, but the input data is restricted to the triangular subarray on one side of the diagonal, giving a dimension of KH=k(k−1)/2 for the HPC. An exemplary HPC is illustrated in FIG. 2.
As a further extension of product code symmetry, consider further a qary product code C with identical row and column codes CS with parameters n=2n′, k, t (where t is the correcting capability or number of errors that can be corrected in a codeword) and rate k/n. Assuming that the component code CS is a reversible qary code implies: (1) if the (n by n)-symbol matrix X is a codeword of C, then so is the transpose matrix XT because the row and column code are the same; and (2) if X is a codeword of C, then so is XF because the row and column code are the same and reversible (where the XF denotes a reflection of matrix X in the anti-diagonal, i.e., the matrix obtained by flipping all elements of X on the anti-diagonal).
For the product code C, the corresponding quarter product code (QPC) CQ is defined as the subcode given by CQ={X−XT-(X−XT)F:X∈C}. By construction, every codeword Y of CQ has a zero diagonal and zero anti-diagonal. By symmetry, the entries in a triangular subarray confined between the two diagonals determine the QPC codeword as illustrated in FIG. 3. Thus, the effective codeword length of the QPC is NQ=(n2−2n)/4=n′2−n′=n′(n′−1).
Further information regarding the construction and use of HPCs and QPCs in encoding and decoding data can be found in T. Mittelholzer, T. Parnell, N. Papandreou, H. Pozidis, “Symmetry-Based Subproduct Codes,” Proc. IEEE Int'l Symp. on Information Theory 2015, Hong Kong, PR of China, June 2015, and in Mittelholzer et al., “Forward correction by block code memory access check bits stored in separate area of memory,” U.S. Patent Publication No. 2015/0309875, which are both incorporated herein by reference.